翻訳と辞書 Words near each other ・ Wallace Stickney ・ Wallace Stovall ・ Wallace Stroby ・ Wallace Sword ・ Wallace T. Foote, Jr. ・ Wallace T. MacCaffrey ・ Wallace Terry ・ Wallace Thayer ・ Wallace Thompson ・ Wallace Thurman ・ Wallace Tillinghast ・ Wallace Townsend ・ Wallace Township ・ Wallace Township, Chester County, Pennsylvania ・ Wallace Township, LaSalle County, Illinois ・ Wallace tree ・ Wallace Trevor Holliday ・ Wallace Triplett ・ Wallace Tripp ・ Wallace Turnage ・ Wallace Turner ・ Wallace v United Grain Growers Ltd ・ Wallace v. Child ・ Wallace v. Cutten ・ Wallace v. International Business Machines Corp. ・ Wallace v. Jaffree ・ Wallace W. Andrew ・ Wallace W. Kirby ・ Wallace W. Waterman Sod House ・ Wallace Wade Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Wallace tree ： ウィキペディア英語版 Wallace tree A Wallace tree is an efficient hardware implementation of a digital circuit that multiplies two integers, devised by Australian Computer Scientist Chris Wallace in 1964.〔 C. S. Wallace, A suggestion for a fast multiplier, IEEE Trans. on Electronic Comp. EC-13(1): 14-17 (1964)〕 The Wallace tree has three steps: # Multiply (that is - AND) each bit of one of the arguments, by each bit of the other, yielding $n^2$ results. Depending on position of the multiplied bits, the wires carry different weights, for example wire of bit carrying result of $a\_2\; b\_3$ is 32 (see explanation of weights below). # Reduce the number of partial products to two by layers of full and half adders. # Group the wires in two numbers, and add them with a conventional adder.〔(Veech engineering )〕 The second phase works as follows. As long as there are three or more wires with the same weight add a following layer: * Take any three wires with the same weights and input them into a full adder. The result will be an output wire of the same weight and an output wire with a higher weight for each three input wires. * If there are two wires of the same weight left, input them into a half adder. * If there is just one wire left, connect it to the next layer. The benefit of the Wallace tree is that there are only $O(\backslash log\; n)$ reduction layers, and each layer has $O(1)$ propagation delay. As making the partial products is $O(1)$ and the final addition is $O(\backslash log\; n)$, the multiplication is only $O(\backslash log\; n)$, not much slower than addition (however, much more expensive in the gate count). Naively adding partial products with regular adders would require $O(\backslash log^2n)$ time. From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC1. These computations only consider gate delays and don't deal with wire delays, which can also be very substantial. The Wallace tree can be also represented by a tree of 3/2 or 4/2 adders. It is sometimes combined with Booth encoding.〔( Tufts university )〕〔(University of Massachusetts, Amherst )〕 ==Weights explained== The weight of a wire is the radix (to base 2) of the digit that the wire carries. In general, $a\_nb\_m$ – have indexes of $n$ and $m$; and since $2^n\; 2^m\; =\; 2^$ the weight of $a\_n\; b\_m$ is $2^$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Wallace tree」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.